package com.example.lc_0005;

/**
 * @author zfj
 * @date 2022/2/28 -15:45
 */
public class Solution {
	public static void main(String[] args) {
		String s = "babad";
		System.out.println(longestPalindrome(s));

	}
	//中心扩散
	public static String longestPalindrome(String s) {
		int len=s.length();
		if(len<2){
			return s;
		}
		int maxLen=1;
		int begin=0;
		//检查数组下表越界，因此先转换为字符数组，
		char[] cs=s.toCharArray();
		//枚举所有长度严格大于1的子串，charArray[i..j]
		for(int i=0;i<len-1;i++){
			int oddLen=expandAroundCenter(cs,i,i);
			int evenLen=expandAroundCenter(cs,i,i+1);
			int curMaxLen=Math.max(oddLen,evenLen);
			if(curMaxLen>maxLen){
				maxLen=curMaxLen;
				//
				begin=i-(maxLen-1)/2;
			}
		}
		return s.substring(begin,begin+maxLen);
	}

	/**
	 * 验证字串是否为回文
	 * @param cs 原始字符串的字符数组
	 * @param i 起始左边界
	 * @param j 起始有边界
	 * @return
	 */
	private static int expandAroundCenter(char[] cs,int i,int j){
		//当i=j回文中心是一个字符，回文串长度是奇数
		//j=i+1 回文中心是两个字符，回文串的长度是偶数
		int len=cs.length;
		while(i>=0&&j<len){
			if(cs[i]==cs[j]){
				i--;
				j++;
			}else {
				break;
			}

		}
		//跳出while循环的时候，恰好满足s.charAt(i)!=s.charAt(j);
		return j-i-1;
	}
}
